'''
https://leetcode.cn/problems/maximum-average-subtree
'''

from typing import Optional
# Definition for a binary tree node.


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:
        def f(root):
            if not root:
                return 0, 0, .0
            l_sum, l_cnt, l_ans = f(root.left)
            r_sum, r_cnt, r_ans = f(root.right)
            sum = l_sum + r_sum + root.val
            cnt = l_cnt + r_cnt + 1
            ans = max(l_ans, r_ans, sum / cnt)
            return sum, cnt, ans
        return f(root)[2]
